package com.ww.springboot.boot.algorithm.leetcode2;

import com.ww.springboot.boot.algorithm.leetcode1.PrintUtil;

import java.util.*;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2025-05-12 10:15
 */
public class B109打开转盘锁 {

    public static void main(String[] args) {
        String[] deadends = new String[]{"7867","6676","8687","7886","6768","8877","6767","6676","6666","7876","6688","6677","6877","7786","6778","6868","6868","7867","7668","7666","8868","7887","6788","7687","7788","7877","6867","6867","7876","8787","8878","6668","6878","6766","8667","8688","6788","7687","8887","8766","6867","8867","7866","7866","6686","7776","8687","7888","6777","6678","6678","6686","6677","7886","6876","8666","6667","7768","7688","7668","6786","7766","7867","8866","7887","6676","8776","6867","8888","6678","8687","6868","7888","8666","6678","6668","7678","7667","8786","8768","6766","8776","8677","7788","7868","7878","6786","6678","6876","7667","8866","8666","8768","8886","8787","8688","8766","8867","7886","6876","7776","7867","8668","7777","8888","7767","8778","8888","6876","8777","7877","8866","8668","8878","7678","8787","7788","8887","8667","7887","6686","8778","7768","8787","7677","6768","7877","7788","7768","6768","6786","7887","7768","6676","6777","8686","7867","8788","8887","8776","7677","8786","8678","7666","8776","7676","6767","8776","8888","8766","8876","7777","7677","6767","7878","7868","8677","7677","8788","6667","8866","8887","6686","6777","6676","8787","6788","8866","6767","8676","8868","8768","8888","7866","7877","7768","7686","7888","6666","6887","6787","7667","6676","8666","8886","8878","8678","8868","8888","8867","7878","7787","8776","7877","6788","8778","6768","8677","8678","6778","7888","6866","6768","6666","6887","8866","7676","7866","7876","7678","7686","8887","7676","6788","8787","6666","8866","6876","8676","8688","8887","7887","7777","8887","8688","6668","6686","6887","7677","6867","6786","6877","7788","6667","8778","8786","8767","7778","8867","8877","6668","8886","7888","7767","7666","8678","8668","8767","7666","6787","6886","8787","6886","8768","8767","8676","6767","8776","8768","8687","8778","7888","6768","7878","6668","7688","6687","7866","8878","6877","7667","8886","7876","6667","8877","7666","7668","7676","6888","6686","7666","7688","7666","6678","6676","7678","8788","7667","7767","8766","6867","8767","8676","8786","8667","6678","6778","8877","8788","6866","7687","6876","8878","8866","6788","6877","8768","8778","8778","8866","7866","7887","7878","8766","8778","7868","8787","6676","8668","7866","8787","8767","6876","8867","6688","6886","6668","6878","7866","8678","8867","7667","7878","8778","8777","7866","8878","7868","6876","7688","7677","7678","7777","8888","8776","8688","6878","8877","7678","7777","7878","6678","6688","6868","8876","6668","8877","8786","6688","8766","8887","6678","8886","8876","8888","8878","6786","7686","7867","7767","7888","8866","6876","7767","6687","6687","6688","6868","8668","6886","8686","7766","8777","8667","8886","7676","7768","6788","8688","7676","7686","8777","7886","7788","6666","7687","6676","6777","6866","6767","7787","7877","6777","6886","7877","7787","7787","8768","7787","8778","6766","7677","6788","6786","6767","8687","6687","8668","6876","6666","7676","8667","6688","6766","6677","7667","8668","8866","7686","8866","8687","8866","8768","7886","6877","8877","6676","6887","6788","8877","8887","8886","8887","6676","8867","6867","7768","8868","6668","7878","7887","8768","6876","7787","7876","8886","6778","7778","7687","6686","7787","8767","8668","7686","7678","8788","6687","8666","7877","6668","7686","6866","6888","8786","7778","7786","8787","6777","6867","7787","7777","6766","8666","6778","6867","8668","8667","7678","8668","7677","8787","6876","6668","7788","7688","7687","8778","8787","8688","8867"};
        String target = "6776";
        long l = System.currentTimeMillis();
        System.out.println(openLock(deadends, target));
        System.out.println(System.currentTimeMillis() - l);
    }


    /**
     * 按照广度优先 每次走一步 穷举所有可能性 去除无效的组合 直到找到目标值
     * 比官方耗时的原因的: 没有用set set查找是否存在只需要O(1) list需要O(n)
     *
     * 涉及到单值查询一定要用set
     *
     * @param deadends
     * @param target
     * @return
     */
    public static int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<String>();
        for (String deadend : deadends) {
            dead.add(deadend);
        }
        if(dead.contains("0000")){
            return -1;
        }
        //不允许走回头路 记录所有历史的路线 不允许走回头路
        Set<String> hisList = new HashSet<>();
        hisList.add("0000");
        //作为每一步的分隔符
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        int step = 0;
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();
                List<String> list = get(poll);
                if(list.contains(target)){
                    System.out.println(hisList.size());
                    return step;
                }
                for (String str : list) {
                    if (!hisList.contains(str) && !dead.contains(str)) {
                        hisList.add(str);
                        queue.add(str);
                    }
                }
            }
        }
        return -1;
    }

    private static boolean combination(String ss, int index, String s, List<String> hisList, List<String> stopList, boolean stop, String target) {
//        if (stop) {
//            String str = ss + s.substring(index);
//            if (!hisList.contains(str) && !stopList.contains(str)) {
//                hisList.add(str);
//            }
//            return;
//        }
//        char c = s.charAt(index);
//        //三种可能 +1 -1 不变
//        if (index == 3) {
//            combination(ss + (char) ((c + 1) > '9' ? '0' : (c + 1)), index + 1, s, hisList, stopList, true);
//            combination(ss + (char) ((c - 1) < '0' ? '9' : (c - 1)), index + 1, s, hisList, stopList, true);
//        } else {
//            combination(ss + (char) ((c + 1) > '9' ? '0' : (c + 1)), index + 1, s, hisList, stopList, true);
//            combination(ss + (char) ((c - 1) < '0' ? '9' : (c - 1)), index + 1, s, hisList, stopList, true);
//            combination(ss + c, index + 1, s, hisList, stopList, false);
//        }

        return false;
    }

    public static char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }

    public static char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }

    // 枚举 status 通过一次旋转得到的数字
    public static List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            ret.add(new String(array));
            array[i] = numSucc(num);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }
}
